import java.text.DecimalFormat  # Python 中不需要，会用字符串格式化和简单计算替代
import java.util.ArrayList     # Python 中用 list 替代
import java.util.Arrays        # Python 中用 list 和内置方法替代

# 参考01背包实现
class TransportGoods2:
    # 货物体积数据 单位立方米 转为立方分米（1 立方米 = 1000 立方分米，这里直接在计算时处理）
    volumeArr = [
        1.18041, 8.92088, 4.58139, 5.29266, 1.23892, 3.93005, 7.53638,
        6.92084, 3.89288, 4.67208, 0.37816, 0.7633, 1.40949, 0.2945, 3.63577, 4.53125,
        6.86774, 7.0336, 3.23038, 3.28645, 0.92165, 6.0227, 6.6724, 2.25087, 6.36347,
        0.91234, 0.4131, 6.02533, 2.10624, 0.94981, 5.49145, 1.84597, 1.64853, 4.24115,
        2.70332, 3.73644, 5.50686, 4.85712, 5.72609, 3.07091, 5.43169, 7.88526, 2.37452,
        2.87198, 6.30832, 3.03664, 3.19001, 3.50305, 0.28338, 9.95386, 3.94953, 6.72467,
        3.82848, 3.03825, 6.21533, 9.27925, 6.87071, 8.19529, 8.23215, 0.75555, 3.89223,
        2.5766, 1.29117, 2.71529, 9.9597, 1.45661, 7.13919, 9.66758, 5.29364, 0.59208, 1.06844,
        6.91517, 6.27877, 1.30585, 2.9094, 6.05222, 1.73932, 6.30585, 1.19917, 4.87037, 1.07854,
        7.28688, 3.50365, 1.64666, 0.5104, 1.01293, 4.91249, 6.23181, 2.64839, 3.06228,
        5.61209, 3.58101
    ]
    capacity = 40 * 1000  # 容量，单位立方分米（对应 Java 中 40 * 1000）

    @staticmethod
    def getMaxVolumeMulti(volumeArr, capacity):
        num = 0
        # 判断货物体积数组中是否还有数据（这里用是否还有非零元素判断，类似 Java 中数组长度是否为 0 的逻辑）
        while any(x > 0 for x in volumeArr):
            num += 1
            arr = TransportGoods2.getMaxVolume(volumeArr, capacity, num)
            # 更新 volumeArr，过滤掉已选中的（置为 0 的元素后续会处理）
            volumeArr = arr

    @staticmethod
    def translate(volumeArr):
        """
        对货物体积数据进行整数化处理（转为立方分米，保留三位小数后再转为整数）
        """
        arr = []
        for v in volumeArr:
            # 先转为立方分米（乘以 1000），保留三位小数，再转为整数
            temp = round(v * 1000, 3)  # 等价于 Java 中保留三位小数后取整
            arr.append(int(temp))
        return arr

    @staticmethod
    def getMaxVolume(volumeArr, capacity, num):
        """
        类似 01 背包求解，返回更新后的体积数组（已选中的置为 0）
        """
        n = len(volumeArr)
        # 定义状态数组，dp[i][j] 表示前 i 个物品，容量为 j 时的最大体积
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            for j in range(1, capacity + 1):
                if j < volumeArr[i - 1]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volumeArr[i - 1]] + volumeArr[i - 1])

        print(f"\n---------------------")
        print(f"第 {num} 辆车，最大组合体积为 {dp[n][capacity]}")
        # 调用打印物品信息方法，并返回更新后的数组
        newArr = TransportGoods2.printGoodsInfo(dp, volumeArr, capacity)
        return newArr

    @staticmethod
    def printGoodsInfo(dp, volumeArr, capacity):
        """
        打印选中的货物信息，并返回更新后的体积数组（选中的置为 0）
        """
        i = len(volumeArr)
        j = capacity
        newArr = volumeArr.copy()  # 复制数组，用于修改
        while i > 0 and j > 0:
            try:
                if dp[i][j] == dp[i - 1][j - newArr[i - 1]] + newArr[i - 1]:
                    # 说明选中了 newArr[i - 1] 这个货物
                    print(f"选择了体积为 {newArr[i - 1]} 货物。")
                    j -= newArr[i - 1]
                    # 标记已选择的物品（置为 0）
                    newArr[i - 1] = 0
            except IndexError:
                pass
            # 不管是否选择了物品，i 都要移动到上一行
            i -= 1
        # 过滤掉为 0 的元素（生成新数组，类似 Java 中过滤掉 0 数据）
        return [x for x in newArr if x > 0]

    @staticmethod
    def getMaxVolume(volumeArr, capacity, num):
        n = len(volumeArr)
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, capacity + 1):
                if j < volumeArr[i - 1]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volumeArr[i - 1]] + volumeArr[i - 1])

        print(f"\n---------------------")
        print(f"第 {num} 辆车，最大组合体积为 {dp[n][capacity]}")
        return TransportGoods2.printGoodsInfo(dp, volumeArr, capacity)


if __name__ == "__main__":
    # 先转换为整数数组（立方分米）
    translated = TransportGoods2.translate(TransportGoods2.volumeArr)
    TransportGoods2.getMaxVolumeMulti(translated, TransportGoods2.capacity)